/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-04-18
 * Time:22:29
 */

/**
 * BM9删除链表的倒数第n个节点
 */

public class removeNthFromEnd {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if (head == null){
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
//        while (fast != null && fast.next != null){
//            slow = slow.next;
//            for (int i = 0; i < n; i++) {
//                fast = fast.next;
//            }
//        }
        // fast先移动n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // slow和fast同时移动，直到fast到达链表尾部
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 要删除的节点是slow的下一个节点
        slow.next = slow.next.next;
        return dummy.next;
    }
}
